package a2022.a20220905;

import java.util.*;

/**
 * @author lenovo
 * @date 2022/9/5
 */
class a {
    static Map<String, TreeNodeTwo> seen = new HashMap<String, TreeNodeTwo>();
    static Set<TreeNodeTwo> repeat = new HashSet<TreeNodeTwo>();

    public static void main(String[] args) {
        TreeNodeTwo root = new TreeNodeTwo(1,
                new TreeNodeTwo(2,
                        new TreeNodeTwo(4),
                        null),
                new TreeNodeTwo(3,
                        new TreeNodeTwo(2,
                                new TreeNodeTwo(4),
                                null),
                        new TreeNodeTwo(4)));
        List<TreeNodeTwo> duplicateSubtrees = findDuplicateSubtrees(root);
        for (int i = 0; i < duplicateSubtrees.size(); i++) {
            System.out.println(duplicateSubtrees.get(i).val);
        }
    }


    public static List<TreeNodeTwo> findDuplicateSubtrees(TreeNodeTwo root) {
        dfs(root);
        return new ArrayList<TreeNodeTwo>(repeat);
    }

    public static String dfs(TreeNodeTwo node) {
        if (node == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(node.val);
        sb.append("(");
        sb.append(dfs(node.left));
        sb.append(")(");
        sb.append(dfs(node.right));
        sb.append(")");
        String serial = sb.toString();
        if (seen.containsKey(serial)) {
            repeat.add(seen.get(serial));
        } else {
            seen.put(serial, node);
        }
        return serial;
    }
}

